package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //求根节点到叶节点数字之和
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode() {}
         *     TreeNode(int val) { this.val = val; }
         *     TreeNode(int val, TreeNode left, TreeNode right) {
         *         this.val = val;
         *         this.left = left;
         *         this.right = right;
         *     }
         * }
         */
        class Solution {
            public int sumNumbers(TreeNode root) {
                // 从根出发，前缀为 0
                return sum(root, 0);
            }

            // 返回以 root 为起点的所有根到叶路径所形成数字的总和，presum 为十进制前缀
            private int sum(TreeNode root, int presum) {
                if (root == null) return 0;               // 空树或空子树贡献为 0

                int cur = presum * 10 + root.val;         // 向下推进十进制前缀
                // 叶子：当前前缀就是完整的路径数字
                if (root.left == null && root.right == null) return cur;

                // 非叶子：汇总左右子树
                return sum(root.left, cur) + sum(root.right, cur);
            }
        }

        //二叉树剪枝
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode() {}
         *     TreeNode(int val) { this.val = val; }
         *     TreeNode(int val, TreeNode left, TreeNode right) {
         *         this.val = val;
         *         this.left = left;
         *         this.right = right;
         *     }
         * }
         */
        class Solution2 {
            public TreeNode pruneTree(TreeNode root) {
                return prune(root);
            }

            // 后序修剪：返回修剪后的子树根
            private TreeNode prune(TreeNode node) {
                if (node == null) return null;

                // 先修剪左右，再决定当前
                node.left = prune(node.left);
                node.right = prune(node.right);

                // 当前结点为 0 且左右都空 -> 该子树不含 1，剪掉
                if (node.val == 0 && node.left == null && node.right == null) {
                    return null;
                }
                return node;
            }
        }
    }
}